#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int val) : val(val), next(nullptr) {}
    ListNode(int val, ListNode *next) : val(val), next(next) {}

    ListNode *append(int val)
    {
        this->next = new ListNode(val);
        return this->next;
    }
};

// 常规做法
ListNode *removeNthFromEnd(ListNode *head, int n)
{
    int total = 0;
    auto tmp = head;
    while (tmp != nullptr)
    {
        tmp = tmp->next;
        total++;
    }

    // 处理删除的节点为第一个节点的情况
    if (n == total)
    {
        return head->next;
    }

    ListNode *pre = head;
    for (int i = 0; i < total - n - 1; i++)
    {
        pre = pre->next;
    }

    pre->next = pre->next->next;

    return head;
}

/* Use double pointer - fast and slow pointers
                       n = 2
                        slow             fast
                         |------ 2 -------|
        dummy  1    2    3    4     5    null
*/
ListNode *removeNthFromEnd2(ListNode *head, int n)
{

    ListNode dummy(0, head);
    ListNode *fast = &dummy;
    ListNode *slow = &dummy;

    // fast move n+1 step
    for (int i = 0; i < n + 1; i++)
    {
        fast = fast->next;
    }

    // move together util fast is null
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }

    slow->next = slow->next->next;

    return dummy.next;
}

void printList(ListNode *head)
{
    cout << "list: " << endl;
    if (head == nullptr)
    {
        cout << "null" << endl;
    }
    while (head != nullptr)
    {
        cout << head->val << endl;
        head = head->next;
    }
}

int main()
{
    ListNode *l1 = new ListNode(1);
    l1->append(2)->append(3)->append(4)->append(5);
    printList(removeNthFromEnd(l1, 2));

    ListNode *l2 = new ListNode(1);
    printList(removeNthFromEnd(l2, 1));

    ListNode *l3 = new ListNode(1);
    l3->append(2);
    printList(removeNthFromEnd(l3, 1));

    return 0;
}